/*************************************************************************
> File Name: mooreVoted.cpp
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2024-01-11 21:23:19
> Description:
169 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。
多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素
************************************************************************/

// 思路：
// 摩尔投票法
#include <vector>
using namespace std;

class Solution
{
public:
    int majorityElement(vector<int> &nums)
    {
        int x = nums[0], vote = 0, length = nums.size();
        for (int i = 0; i < length; i++)
        {
            if (vote == 0)
            {
                x = nums[i];
            }
            nums[i] == x ? vote++ : vote--;
        }
        return x;
    }
};
